A processing system may comprise one or more processors which can make requests for accessing data stored in a memory (e.g., a main memory implemented in a double data rate (DDR) implementation using dynamic random access memory (DRAM) technology). Memory requests generated by a processor may display temporal locality, which means that the requests are directed to data which was recently requested, and correspondingly also means that the same data may be requested again in the near future. To exploit temporal locality, one or more caches may be provided to store data which is determined to have likelihood of future use. The caches may be designed to be small in size to enable high speeds (e.g., in the order of few tens of clock cycles, as compared to memory access speeds which can be in the order of hundreds or thousands of clock cycles).
If the requested data is present in the cache, a cache hit results and the data can be read directly from the cache which produced the cache hit. On the other hand, if the requested data is not present in the cache, a cache miss results, and backing storage locations such as other caches or ultimately the memory may be accessed to retrieve the requested data. Since the caches are designed to be small, the limited storage space in the caches may be filled up, which means that some cache lines may need to be evicted (called victim cache lines) to accommodate incoming cache lines (called contender cache lines). Cache replacement policies are known in the art for evicting the victim cache lines and replacing them with the contender cache lines. The process of selecting which cache lines to evict is referred to as victim selection.
A last-level cache, such as an L3 cache is a backing storage location before main memory for processors and higher level caches such as L1 and L2 caches. A study of access characteristics of last-level caches reveals that a number of cache lines which were inserted in the last-level caches (e.g., upon replacing victim cache lines) may never be reused or accessed again before they are themselves evicted. Thus, these cache lines may not have served a useful purpose during their tenure in the last level cache. Moreover, these cache lines which were not reused may have displaced victim lines which may have been more useful (i.e., may have been reused) had they not been evicted. Conventional victim selection policies are designed to select a victim cache line with a low or least likelihood of future use as a candidate for eviction; but the victim selection policies do not take into account a relative usefulness or reuse potential for a contender cache line which displaces the victim cache line. Thus, there may be scenarios where a more useful cache line is replaced by a less useful cache line, e.g., in last-level caches, but these scenarios are not prevented by conventional cache management policies.